package com.study.lu;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class 素数 {
    /**
     * 求0-100中的素数
     * 素数：只能被自己整除的数,0 1除外  eg  2 3 5 7 11
     *
     * @param args
     */
    public static void main(String[] args) {

        List<Integer> resList = bf(100);

        resList = asf(100);
        System.out.println("素数个数：" + resList.size() + ",值为：" + resList.stream().map(v -> String.valueOf(v)).collect(Collectors.joining(",")));
    }

    /**
     * 埃筛法
     * 只要知道一个数是素数，那么这个数的乘积（>=2）必然不是素数    eg 2是素数  2*2=4不是素数 2*3不是素数
     *
     * @param num
     * @return
     */
    private static List<Integer> asf(int num) {
        List<Integer> resList = new ArrayList<>(10);
        boolean[] nums = new boolean[num];
        for (int i = 2; i <= num; i++) {
            // 非素数 直接跳过
            if (nums[i-1]) {
                continue;
            }
            if (isSuShu2(i)) {
                resList.add(i);
                for (int j = 2; j * i <= num; j++) {
                    nums[j * i-1] = true;
                }
            }
        }
        return resList;

    }

    private static List<Integer> bf(int num) {
        List<Integer> resList = new ArrayList<>(10);
        for (int i = 2; i <= num; i++) {
            if (isSuShu2(i)) {
                resList.add(i);
            }
        }
        return resList;
    }

    /**
     * 一个非素数 只需要遍历 到一半即可 如下示例
     * eg   12  乘积如下
     * 2*6=12
     * 3*4=12
     * 4*3=12
     * 6*2=12
     *
     * @param num
     * @return
     */
    private static boolean isSuShu2(int num) {
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static boolean isSuShu(int num) {
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}
